我们只需尽可能的在区间 内寻找质因子数量最多的数,再与 的质因子数量比较即可。
考虑到 增长速度相比于其他质数 要慢,而对于和 大小相近的数,他们的质因子个数不可能比 要多。
我们可以感性理解这一件事情,于是我们就得到了第一个结论:
- 在区间 中,质因子个数最多的数为最大的形如 的数,即找到 。
这一件事情可以在 的时间内做到。
然后就可以去比较 的质因子个数与 的大小了。
由于 ,分解质因数 的方式肯定是不可行的,那我们便使用一些奇技淫巧更高端的技巧。
我们考虑 的一些特殊情况:
-
当 为奇数时, 中不含有质因子 ,此时我们可以感性理解一下,要想用奇质数乘出大小差不多的数,用到的质数个数会更少,所以 的质因子个数必定小于 ,即 。
-
当 时,此时虽然 已经是最大的了,但 中有 个质因子,所以 的质因子个数大于 ,即 。
-
当 时,此时 正好介于 与 之间,但质因子个数也是 ,故 。
-
对于其他的偶数 ,我们可以用第一类中的方法类似理解一下,质因子个数应该也是小于 的,即 。
综上所述,我们便可以用特判的方法过掉这一道题了,时间复杂度 。
还有就是注意一些细节,比如左移记得要用 long long 。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
int main() {
int T; scanf("%d", &T);
while (T--) {
long long n; scanf("%lld", &n);
int k = 0;
while (1LL << (k + 1) < n) k++;
if (n >= 5 && n % 2 == 1) puts("1");
else if (n % 3 == 0 && 1LL << (k - 1) == n / 3) puts("0");
else if (n % 2 == 0 && 1LL << (k + 1) == n) puts("0");
else puts("1");
}
}